#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2022/5/11 20:21
# @Author  : Yizheng Dai
# @Email   : 387942239@qq.com
# @File    : _112_hasPathSum.py
from typing import List

from _22_backtracking_algorithmI.treenode import TreeNode

from copy import deepcopy

class Solution(object):
    def hasPathSum(self, root:TreeNode, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: bool
        """
        res = []
        path = []

        self.dfs(root, path, res)

        for path in res:
            total = sum(path)
            if total==targetSum:
                return True
        return False


    def dfs(self, node:TreeNode, path:List, res:List[List])->None:
        if node == None:
            return
        path.append(node.val)
        if node.left==None and node.right==None:
            res.append(deepcopy(path))

        self.dfs(node.left, path, res)
        self.dfs(node.right, path,res)

        path.pop(len(path)-1)


    ## 返回值
    def hasPathSum1(self, root: TreeNode, targetSum):
        return self.dfs1(root, targetSum)

    def dfs1(self, node:TreeNode, target):
        if node == None:
            return False

        current_target = target - node.val
        if node.left==None and node.right==None:
            return current_target == 0

        is_left_path = self.dfs1(node.left, current_target)
        if is_left_path:
            return True
        is_right_path = self.dfs1(node.right, current_target)

        return is_left_path or is_right_path




